<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png?v=5.1.4">


  <link rel="mask-icon" href="/images/favicon.png?v=5.1.4" color="#222">





  <meta name="keywords" content="C++," />





  <link rel="alternate" href="/atom.xml" title="平步青云win" type="application/atom+xml" />






<meta name="description" content="面试中常见的算法题目。">
<meta name="keywords" content="C++">
<meta property="og:type" content="article">
<meta property="og:title" content="算法和数据结构">
<meta property="og:url" content="https://zxpgo.github.io/2019/10/12/算法和数据结构/index.html">
<meta property="og:site_name" content="平步青云win">
<meta property="og:description" content="面试中常见的算法题目。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190902142227.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190903203101.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190923084839.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190923084910.png">
<meta property="og:image" content="c:/Users/zxp/AppData/Roaming/Typora/typora-user-images/1569199954806.png">
<meta property="og:image" content="c:/Users/zxp/AppData/Roaming/Typora/typora-user-images/1569322792414.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925144546.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925144947.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925184730.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925193310.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925200822.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925202734.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927202113.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927203057.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927210719.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190930133603.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002152730.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002153607.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002154655.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002155621.png">
<meta property="og:image" content="c:/Users/zxp/AppData/Roaming/Typora/typora-user-images/1570003668165.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002161222.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002162550.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002212043.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002212847.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003085016.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003085706.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003090329.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003090356.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003091645.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003091810.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003092700.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003093259.png">
<meta property="og:updated_time" content="2019-11-18T13:07:21.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法和数据结构">
<meta name="twitter:description" content="面试中常见的算法题目。">
<meta name="twitter:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20190902142227.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":10,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: 'PAO8LM7QB1',
      apiKey: '',
      indexName: 'Blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://zxpgo.github.io/2019/10/12/算法和数据结构/"/>





  <title>算法和数据结构 | 平步青云win</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?7a4517a3ce6d7c50203655d056f01ac3";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">平步青云win</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description"></h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-随笔">
          <a href="/sui" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            随笔
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
			
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://zxpgo.github.io/2019/10/12/算法和数据结构/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="zxp">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平步青云win">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">算法和数据结构</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-10-12T11:44:14+08:00">
                2019-10-12
              </time>
            

            

            
          </span>

          

          
            
          

          
          
             <span id="/2019/10/12/算法和数据结构/" class="leancloud_visitors" data-flag-title="算法和数据结构">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数&#58;</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <p>面试中常见的算法题目。</p>
<a id="more"></a>
<h1 id="实现Memmove"><a href="#实现Memmove" class="headerlink" title="实现Memmove"></a>实现Memmove</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> * <span class="title">memmove</span><span class="params">(<span class="keyword">void</span> *dest, <span class="keyword">void</span> * src, <span class="keyword">size_t</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">char</span> * p1 = dest;</span><br><span class="line">    <span class="keyword">char</span> * p2 = src;</span><br><span class="line">    whle(*p2 != <span class="string">'\0'</span>)</span><br><span class="line">        *p1++ = *p2++;</span><br><span class="line">    <span class="keyword">return</span> p1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="C语言的陷阱"><a href="#C语言的陷阱" class="headerlink" title="C语言的陷阱"></a>C语言的陷阱</h2><ul>
<li>内存重叠的处理</li>
<li>临时变量太多或者没有安全释放</li>
<li>没有测试内存越界</li>
<li>指针操作不熟悉</li>
</ul>
<h3 id="内存重叠"><a href="#内存重叠" class="headerlink" title="内存重叠"></a>内存重叠</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190902142227.png" alt=""></p>
<p>对于内存重叠的情况，从尾到到头开始赋值。</p>
<h2 id="正确写法"><a href="#正确写法" class="headerlink" title="正确写法"></a>正确写法</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> * <span class="title">memmove</span><span class="params">(<span class="keyword">void</span> *dest, <span class="keyword">const</span> <span class="keyword">void</span> * src, <span class="keyword">size_t</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">char</span> * p1 = dest;</span><br><span class="line">    <span class="keyword">const</span> <span class="keyword">char</span> * p2 = src;</span><br><span class="line">    <span class="keyword">if</span> (p2 &lt; p1)&#123;</span><br><span class="line">        p2 += n;</span><br><span class="line">        p2 += n;</span><br><span class="line">        <span class="keyword">while</span>(n-- != <span class="number">0</span>)</span><br><span class="line">            *--p1 = *--p2;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">while</span>(n-- != <span class="number">0</span>)</span><br><span class="line">            *p1++ = *p2++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> p1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="面试考察的变成基本功"><a href="#面试考察的变成基本功" class="headerlink" title="面试考察的变成基本功"></a>面试考察的变成基本功</h1><ul>
<li>编程风格：缩进，括号，变量名</li>
<li>编程习惯：异常检查，边界处理</li>
<li>沟通：让面试官时刻明白你的意图</li>
<li>测试：主动写出合理的Testcase</li>
</ul>
<h2 id="代码风格"><a href="#代码风格" class="headerlink" title="代码风格"></a>代码风格</h2><ul>
<li>变量的命名：有意义的变量名，第一个单词的首字母小写，后面单词的首字母大写。</li>
<li>缩进：语句块</li>
<li>空格：运算符两边</li>
<li>代码可读性</li>
</ul>
<p>类名大写。函数名首字母大写。变量名多个单词构成，第一个单词的首字母小写，后面单词的首字母大写。</p>
<p>一个函数只做一件事。</p>
<h2 id="实战算法策略"><a href="#实战算法策略" class="headerlink" title="实战算法策略"></a>实战算法策略</h2><ul>
<li>总结归类相似题目</li>
<li>找出适合同一类题目的模板程序</li>
<li>对基础题数量掌握</li>
</ul>
<h2 id="排列组合模板"><a href="#排列组合模板" class="headerlink" title="排列组合模板"></a>排列组合模板</h2><h3 id="全排列"><a href="#全排列" class="headerlink" title="全排列"></a>全排列</h3><p>字符串”abc“的全排列。abc,acb,bac,….</p>
<p>无重复的全排序：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Permutation</span><span class="params">(<span class="keyword">char</span> * pstr, <span class="keyword">char</span> * pBegin)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!pStr &amp;&amp; !pBegin)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (*pBegin == <span class="string">'\0'</span>)</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; *pStr &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">char</span> * pCh = pBegin; * pCh != <span class="string">'\0'</span>; pCh++)&#123;</span><br><span class="line">            swap(*pBegin, *pCh);</span><br><span class="line">            Permutation(pStr, pBegin+<span class="number">1</span>);</span><br><span class="line">            swap(*pBegin, *pCh);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="组合问题"><a href="#组合问题" class="headerlink" title="组合问题"></a>组合问题</h3><p>题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。</p>
<p>对于每一个元素，可以有选或不选两个状态，因而从排列第一个元素开始，不选它然后求解S[2:n]的全自己；选它然后求解S[2:n]的全子集，两个结构的合并就是整个集合的全子集了。</p>
<h1 id="Array-amp-String"><a href="#Array-amp-String" class="headerlink" title="Array &amp; String"></a>Array &amp; String</h1><h2 id="入门题看String-match"><a href="#入门题看String-match" class="headerlink" title="入门题看String match"></a>入门题看String match</h2><p>两种比较易于实现的字符串比较算法。</p>
<p>假设在长度为n的母串中匹配长度为m的子串。</p>
<h4 id="暴力求解"><a href="#暴力求解" class="headerlink" title="暴力求解"></a>暴力求解</h4><p>顺序遍历母串，将每个字符作为匹配的起始字符，判断是否匹配子串。时间复杂度为o(m×n)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//本人自己所写</span></span><br><span class="line"><span class="function"><span class="keyword">char</span> * <span class="title">strStr</span><span class="params">(<span class="keyword">const</span> <span class="keyword">char</span> * str, <span class="keyword">const</span> <span class="keyword">char</span> * target)</span> </span>&#123;</span><br><span class="line">	<span class="comment">//边界条件考虑</span></span><br><span class="line">	<span class="keyword">if</span> (!*str || !*target)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">char</span> * beginTarget = (<span class="keyword">char</span> *)target;</span><br><span class="line">	<span class="keyword">char</span> * beginStr = (<span class="keyword">char</span> *)str;</span><br><span class="line">	<span class="keyword">while</span> (*target != <span class="string">'\0'</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (*str == <span class="string">'\0'</span>)</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">		<span class="keyword">if</span> (*target == *str) &#123;</span><br><span class="line">			target++;</span><br><span class="line">			str++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			beginStr++;</span><br><span class="line">			str = beginStr;</span><br><span class="line">			target = beginTarget;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">const_cast</span>&lt;<span class="keyword">char</span> *&gt;(str - <span class="built_in">strlen</span>(beginTarget));</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//视频中代码</span></span><br><span class="line"><span class="function"><span class="keyword">char</span> * <span class="title">strStr</span><span class="params">(<span class="keyword">const</span> <span class="keyword">char</span> * str, <span class="keyword">const</span> <span class="keyword">char</span> * target)</span> </span>&#123;</span><br><span class="line">	<span class="comment">//边界条件考虑</span></span><br><span class="line">	<span class="keyword">if</span> (!*str || !*target)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">char</span> * pStr = (<span class="keyword">char</span> *)str;</span><br><span class="line">	<span class="keyword">while</span> (*pStr) &#123;</span><br><span class="line">		<span class="keyword">char</span> * pBegin = pStr, *pTarget = (<span class="keyword">char</span>*)target;</span><br><span class="line">		<span class="keyword">while</span> (*pStr &amp;&amp; *pTarget &amp;&amp; *pStr++ == *pTarget++) &#123;&#125;</span><br><span class="line">		<span class="keyword">if</span> (!*pTarget)</span><br><span class="line">			<span class="keyword">return</span> pBegin;</span><br><span class="line">		pStr = pBegin + <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="Rabin-Karp"><a href="#Rabin-Karp" class="headerlink" title="Rabin-Karp"></a>Rabin-Karp</h4><p>将每一个匹配子串映射为一个hash值。例如，将子串看做一个多进制数，比较它的值与母串中相同长度子串的hash值，如果相同，再细致地按字符确认字符串是否确实相同。顺序计算母串hash值的过程中，使用增量计算的方法：扩初最高位的hash值，增加最低位的hash值。因此能在平均情况下做到o(m+n)。</p>
<p>伪码：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190903203101.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="comment">//Mask 函数用来生成一个字符串的编码</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Mask</span><span class="params">(<span class="built_in">string</span> str, <span class="keyword">const</span> <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> mask = <span class="number">1</span> &lt;&lt; (str[<span class="number">0</span>] - <span class="string">'a'</span>);</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">		mask |= <span class="number">1</span> &lt;&lt; (str[i] - <span class="string">'a'</span>);;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> mask;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">strStr</span><span class="params">(<span class="built_in">string</span> str,<span class="built_in">string</span> target)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> lenOfTarget = target.length();</span><br><span class="line">	<span class="keyword">int</span> lenOfStr = str.length();</span><br><span class="line">	<span class="keyword">int</span> maskTarget = Mask(target, lenOfTarget);</span><br><span class="line">	<span class="keyword">int</span> maskStr = Mask(str, lenOfTarget);</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; lenOfStr - lenOfTarget + <span class="number">1</span>; i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (maskStr == maskTarget) &#123;</span><br><span class="line">			<span class="keyword">if</span> (str.substr(i, lenOfTarget) == target) <span class="comment">//substr()获取string的一个子串，第一个参数是起始位置，第二个参数是子串长度</span></span><br><span class="line">				<span class="keyword">return</span> i;</span><br><span class="line">		&#125;</span><br><span class="line">		maskStr = Mask(str.substr(i+<span class="number">1</span>,i+lenOfTarget), lenOfTarget);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line">	<span class="built_in">string</span> str = <span class="string">"abdcabcda"</span>;</span><br><span class="line">	<span class="built_in">string</span> str2 = <span class="string">"abc"</span>;</span><br><span class="line">	<span class="keyword">int</span> c = strStr(str, str2);</span><br><span class="line">	<span class="keyword">if</span> (c)</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; c &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">std</span>::<span class="built_in">cout</span> &lt;&lt; <span class="string">"Hello World!\n"</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>还有一种方法实现就是KMP，比较复杂。</p>
<h2 id="Array"><a href="#Array" class="headerlink" title="Array"></a>Array</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> <span class="built_in">array</span>[arraySize]; <span class="comment">//在Stack上定义一个长度为arraySize的整型数组</span></span><br><span class="line"><span class="keyword">int</span> * <span class="built_in">array</span> = <span class="keyword">new</span> <span class="keyword">int</span>[arraySize]; <span class="comment">//在Heap上定义长度为arraySize的整型数组</span></span><br><span class="line"><span class="comment">//使用完后需要释放内存</span></span><br><span class="line"><span class="keyword">delete</span> [] <span class="built_in">array</span>;</span><br></pre></td></tr></table></figure>
<p>Stack主要是由操作系统自动管理的内存空间。但进入一个函数，操作系统会为该函数中的局部遍历分配存储空间。事实上，系统会分配一个内存块，叠加在当前的stack上，并且利用指针指向前一个内存块的地址。</p>
<p>函数的局部变量就存储在当前的内存块上。当该函数返回时，系统“弹出”内存块，并且根据指针回到前一个内存块。所以Stack总是以先进先出的方式工作。</p>
<p>Heap是用来存储动态分配变量的空间。对于Heap而言，并没有像stack那样后进先出的规则，程序员可以选择随时分配或回收内存。这就意味着程序员要自己用命令回收内存，否则会产生内存泄漏。</p>
<h3 id="二维数组"><a href="#二维数组" class="headerlink" title="二维数组"></a>二维数组</h3><p>在stack上创建：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> <span class="built_in">array</span>[M][N];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">func</span><span class="params">(<span class="keyword">int</span> arr[M][N])</span></span>&#123;&#125; <span class="comment">//M可以省略，但是N必须存在</span></span><br></pre></td></tr></table></figure>
<p>在Heap上创建：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> **<span class="built_in">array</span> = <span class="keyword">new</span> <span class="keyword">int</span>*[M];</span><br><span class="line"><span class="comment">//C语言</span></span><br><span class="line"><span class="keyword">int</span> <span class="built_in">array</span> =  (<span class="keyword">int</span>**)<span class="built_in">malloc</span>(M * <span class="keyword">sizeof</span>(<span class="keyword">int</span>*));</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; M; i++)</span><br><span class="line">    <span class="built_in">array</span>[i] =  <span class="keyword">new</span> <span class="keyword">int</span>[N]; </span><br><span class="line">	<span class="comment">//C语言</span></span><br><span class="line">	<span class="built_in">array</span>[i] =  (<span class="keyword">int</span>*)<span class="built_in">malloc</span>(N * <span class="keyword">sizeof</span>(<span class="keyword">int</span>));</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">func</span><span class="params">(<span class="keyword">int</span> **arr, <span class="keyword">int</span> M, <span class="keyword">int</span> N)</span></span>&#123;&#125;</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; M; i++)</span><br><span class="line">    <span class="keyword">delete</span>[] <span class="built_in">array</span>[i];</span><br><span class="line"><span class="keyword">delete</span>[] <span class="built_in">array</span>;</span><br></pre></td></tr></table></figure>
<p>array不适合增减元素的场景。</p>
<h3 id="vector"><a href="#vector" class="headerlink" title="vector"></a>vector</h3><p>vector可以用[]直接访问元素。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;::iterator it = v.begin(); it != v.end();)&#123;</span><br><span class="line">    <span class="keyword">if</span> (condition)</span><br><span class="line">        it =v. erase(it); <span class="comment">//返回删除it后的下一个有效元素</span></span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        it++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="Hash-Table"><a href="#Hash-Table" class="headerlink" title="Hash Table"></a>Hash Table</h3><p>Hash table几乎是最为重要的数据结构，主要用于基于“key”的查找，存储的元素基本元素是key-value的pair。逻辑上，数组可以作为Hash Table的一个特例：key是一个非负整数。</p>
<p>插入、删除和查找的时间复杂度都是o(1)。</p>
<h4 id="碰撞"><a href="#碰撞" class="headerlink" title="碰撞"></a>碰撞</h4><ul>
<li><p>开址法</p>
</li>
<li><p>拉链法</p>
</li>
</ul>
<p>Java中的数据结构：</p>
<ul>
<li>Hash Table：同步的</li>
<li>HashSet：在HashMap上省掉了value的值</li>
<li>HashMap：不同步的，对于非线程效率更高的</li>
</ul>
<p>C++中：</p>
<p>提供了map容器，可以插入、删除，查找；底层以红黑树实现的。</p>
<p>在C++11中，标准库中天骄了unordered_map使用Hash Table实现的。</p>
<h2 id="string"><a href="#string" class="headerlink" title="string"></a>string</h2><p>在C语言中，字符串指的是一个以‘\0’结尾的char数组。关于字符串的函数通常需要传入一个字符型指针。常用函数：</p>
<ul>
<li><p>strcpy</p>
</li>
<li><p>strcat</p>
</li>
<li><p>strstr</p>
</li>
<li><p>strcmp</p>
</li>
<li><p>strlen</p>
</li>
<li><p>atoi</p>
</li>
</ul>
<p>C++中string就是一个类，类中重载了+，&lt;,&gt;,=,==等操作符。常用函数：</p>
<ul>
<li>find</li>
<li>substr</li>
<li>erase</li>
<li>length</li>
</ul>
<h2 id="字符串中字符是否唯一"><a href="#字符串中字符是否唯一" class="headerlink" title="字符串中字符是否唯一"></a>字符串中字符是否唯一</h2><p>判断一个字符串在字符串中是否只出现过一次。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bitset&gt;</span></span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isUnique</span><span class="params">(<span class="built_in">string</span> str)</span> </span>&#123;</span><br><span class="line">	<span class="built_in">bitset</span>&lt;256&gt; hashMap; <span class="comment">//长度256，bitset用来存储0或1，true或false</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; str.length(); ++i) &#123;</span><br><span class="line">		<span class="keyword">if</span> (hashMap[(<span class="keyword">int</span>)str[i]]) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		hashMap[(<span class="keyword">int</span>)str[i]] = <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="两个字符串的是否为排列"><a href="#两个字符串的是否为排列" class="headerlink" title="两个字符串的是否为排列"></a>两个字符串的是否为排列</h2><p>无论如何变化，每个字符出现的次数一定相同。一旦需要统计一个元素集中元素出现的次数，就应该考虑使用hash table。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;unordered_map&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isPermutation</span><span class="params">(<span class="built_in">string</span> str1, <span class="built_in">string</span> str2)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (str1.length() != str2.length())</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">	<span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; hashMapStr1;</span><br><span class="line">	<span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; hashMapStr2;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; str1.length(); ++i) &#123;</span><br><span class="line">		hashMapStr1[str1[i]]++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; str2.length(); ++i) &#123;</span><br><span class="line">		hashMapStr2[str2[i]]++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (hashMapStr1.size() != hashMapStr2.size())</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">auto</span> ite = hashMapStr1.begin(); ite != hashMapStr1.end(); ++ite) &#123;</span><br><span class="line">		<span class="keyword">if</span> (ite-&gt;second != hashMapStr2[ite-&gt;first])</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="字符串包含"><a href="#字符串包含" class="headerlink" title="字符串包含"></a>字符串包含</h2><p>给定一个newspaper和message两个字符串，检查是否message可以由newspaper中的字母所组成。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;unordered_map&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">canCompose</span><span class="params">(<span class="built_in">string</span> newspaper, <span class="built_in">string</span> message)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (message.size() == <span class="number">0</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	<span class="keyword">if</span> (newspaper.size() == <span class="number">0</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	<span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; hashMap;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; newspaper.size(); ++i) &#123;</span><br><span class="line">		hashMap[newspaper[i]]++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; message.size(); ++i) &#123;</span><br><span class="line">		hashMap[message[i]]--;</span><br><span class="line">		<span class="keyword">if</span> (hashMap[message[i]] &lt; <span class="number">0</span>)</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="anagram-字谜"><a href="#anagram-字谜" class="headerlink" title="anagram(字谜)"></a>anagram(字谜)</h2><p>决定两个字符串是否是字谜。</p>
<p>比如：s=’abcd’, t=’dcab’ , return true</p>
<p>要求，时间复杂度o(n)，空间复杂度o(1)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">Anagram</span><span class="params">(<span class="built_in">string</span> s, <span class="built_in">string</span> t)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (s.size() != t.size())</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	<span class="keyword">if</span> (s.size() == <span class="number">0</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	sort(s.begin(), s.end());</span><br><span class="line">	sort(t.begin(), t.end());</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.size(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (s[i] != t[i])</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="两数之和在数组中"><a href="#两数之和在数组中" class="headerlink" title="两数之和在数组中"></a>两数之和在数组中</h2><p>判断两个数的和是否存在数组之中。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;map&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; addsToTarget(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;numbers, <span class="keyword">int</span> target) &#123;</span><br><span class="line">	<span class="built_in">map</span>&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; hashMap;</span><br><span class="line">	<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; numbers.size(); ++i) &#123;</span><br><span class="line">		<span class="keyword">if</span> (hashMap.count(target - numbers[i])) &#123;</span><br><span class="line">			res.push_back(hashMap[target-numbers[i]]);</span><br><span class="line">			res.push_back(i);</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		hashMap[numbers[i]] = i;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="数组中连续序列"><a href="#数组中连续序列" class="headerlink" title="数组中连续序列"></a>数组中连续序列</h2><p>求出数组中最长连续序列的长度。例如，给定数组[31,6,32,1,3,2]，最长连续序列为[1,2,3]。返回它的长度3。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Bound</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> low;</span><br><span class="line">	<span class="keyword">int</span> high;</span><br><span class="line">	Bound(<span class="keyword">int</span> l = <span class="number">0</span>, <span class="keyword">int</span> h = <span class="number">0</span>):low(l), high(h)&#123;&#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">longestConsecutive</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;num)</span> </span>&#123;</span><br><span class="line">	<span class="built_in">unordered_map</span>&lt;<span class="keyword">int</span>, Bound&gt; table;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> local = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> maxLen = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; num.size(); ++i) &#123;</span><br><span class="line">		<span class="keyword">if</span> (table.count(num[i]))<span class="comment">//跳过重复元素</span></span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		local = num[i];</span><br><span class="line"></span><br><span class="line">		<span class="keyword">int</span> low = local, high = local;</span><br><span class="line">        <span class="comment">//判断小1或大1的元素是否在table中</span></span><br><span class="line">		<span class="keyword">if</span> (table.count(local - <span class="number">1</span>))  </span><br><span class="line">			low = table[local - <span class="number">1</span>].low;</span><br><span class="line">		<span class="keyword">if</span> (table.count(local + <span class="number">1</span>))</span><br><span class="line">			high = table[local + <span class="number">1</span>].high;</span><br><span class="line"></span><br><span class="line">		table[low].high = table[local].high = high;</span><br><span class="line">		table[high].low = table[local].low = low;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span> (high -  low + <span class="number">1</span> &gt; maxLen)</span><br><span class="line">			maxLen = high - low + <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> maxLen;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="Longest-Common-SubString最长相同子字符串"><a href="#Longest-Common-SubString最长相同子字符串" class="headerlink" title="Longest Common SubString最长相同子字符串"></a>Longest Common SubString最长相同子字符串</h2><p>例如：</p>
<p>str1=”ABCD”, str2=”CBCE”，return 2.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">longestCommonSubString</span><span class="params">(<span class="built_in">string</span> &amp;A, <span class="built_in">string</span> &amp;B)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (A.empty() || B.empty())</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> lcs = <span class="number">0</span>, lcs_temp = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; A.size(); ++i)</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; B.size(); j++) &#123;</span><br><span class="line">			lcs_temp = <span class="number">0</span>;</span><br><span class="line">			<span class="keyword">while</span> (i + lcs_temp &lt; A.size() &amp;&amp; j + lcs_temp &lt; B.size() </span><br><span class="line">                   &amp;&amp; A[i + lcs_temp] == B[j + lcs_temp])</span><br><span class="line">				++lcs_temp;</span><br><span class="line">			<span class="keyword">if</span> (lcs &lt; lcs_temp)</span><br><span class="line">				lcs = lcs_temp;</span><br><span class="line">		&#125;</span><br><span class="line">	<span class="keyword">return</span> lcs;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h1><ul>
<li>反转链表</li>
<li>链表的倒数第k个节点</li>
<li>深度拷贝链表（链表节点有随机指针）</li>
<li>链表有环判断，入口节点</li>
<li>链表的顺序遍历和逆序遍历相同</li>
<li>合并两个有序链表，合并K个有序 链表</li>
</ul>
<h1 id="栈和队列"><a href="#栈和队列" class="headerlink" title="栈和队列"></a>栈和队列</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; myStack;</span><br><span class="line">myStack.push(<span class="number">10</span>);</span><br><span class="line">myStack.push(<span class="number">20</span>);</span><br><span class="line"><span class="keyword">int</span> value = myStack.top();</span><br><span class="line">myStack.pop();</span><br><span class="line"></span><br><span class="line"><span class="built_in">queue</span>&lt;<span class="keyword">int</span>&gt; myQueue;</span><br><span class="line">myQueue.push(<span class="number">10</span>);</span><br><span class="line">myQueue.push(<span class="number">20</span>);</span><br><span class="line"><span class="keyword">int</span> value = myQueue.front();</span><br><span class="line">myQueue.pop();</span><br></pre></td></tr></table></figure>
<p>栈经常用于实现深度优先算法(DFS)。</p>
<p>队列经常用于实现广度优先算法(BFS)。</p>
<p>堆：</p>
<ul>
<li>通过stack实现特殊顺序的读取：通常需要两个stack</li>
<li>通过栈实现队列 </li>
<li>对栈进行排序，借用一个栈使用</li>
<li>有效的括号， 比如“([])”, “[(}]”</li>
<li>解决Top-Down结构的问题，比如：二叉树的周游问题，二叉树的中序遍历</li>
<li>后缀表达式计算</li>
</ul>
<p>队列：</p>
<ul>
<li>循环队列</li>
<li>优先队列</li>
</ul>
<h1 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h1><ul>
<li><p>完全二叉树：只有最下面两层节点的度数可以小于2，并且最下面的节点集中在该层最左侧</p>
</li>
<li><p>满二叉树：二叉树的任意节点要么是叶子节点，要么是度为2的节点，不存在度为1的节点。</p>
</li>
</ul>
<p>二叉树的遍历：</p>
<ul>
<li>前序遍历：根-&gt;左节点-&gt;右节点</li>
<li>中序遍历：左节点-&gt;根-&gt;右节点</li>
<li>后序遍历：左节点-&gt;叶节点-&gt;根</li>
</ul>
<p>三种遍历方式都是深度优先算法，优先考虑递归实现，也可以使用栈数据结构实现。</p>
<p>广度优先遍历：首先访问第一层，然后第二层，依此类推</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190923084839.png" alt=""></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190923084910.png" alt=""></p>
<p><img src="C:\Users\zxp\AppData\Roaming\Typora\typora-user-images\1569199954806.png" alt="1569199954806"></p>
<h2 id="分治算法"><a href="#分治算法" class="headerlink" title="分治算法"></a>分治算法</h2><p>步骤：分解，解决，合并</p>
<ul>
<li>二分搜索</li>
<li>大整数乘法</li>
<li>归并排序</li>
<li>快速排序</li>
</ul>
<h2 id="二分查找树"><a href="#二分查找树" class="headerlink" title="二分查找树"></a>二分查找树</h2><p>对于二分查找树的任意节点，该节点存储的数值一定比左子树的所有节点的值大，比右子树的所有节点的值小。</p>
<p>中序遍历二分查找树得到一个升序的序列。</p>
<p>由于二叉树第L层至多可以存储2^L个节点，故树的高度应该在logn量级，因此，二叉搜索树的搜索效率为o(longn)。</p>
<p>如果退化为一个右小到大的单链表（每个节点只有右孩子），其搜索效率变为o(n)。</p>
<p>判断一棵树是否为二叉搜索树：</p>
<ul>
<li>第一种方法：通过中序遍历得到序列，然后判断是否为升序的</li>
<li>第二种方法：同时传入最小/最大值，并且见初始值设为INT_MAX，INT_MAX，这样左子树所有节点的值必须在INT_MIN及根节点的值之间，其右子树所有节点的值必须在根节点的值以及INT_MAX之间。</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">helper</span><span class="params">(TreeNode* root, <span class="keyword">int</span> min, <span class="keyword">int</span> max)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == root)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">if</span>((root-&gt;val &lt; max || (root-&gt;val == max &amp;&amp; root-&gt;right == <span class="literal">nullptr</span>)) &amp;&amp;</span><br><span class="line">       (root-&gt;val &gt; min || (root-&gt;val == min &amp;&amp; root-&gt;left == <span class="literal">nullptr</span>)))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> helper(root-&gt;left, min, root-&gt;val) &amp;&amp;</span><br><span class="line">            helper(root-&gt;right, root-&gt;val, max);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isValidBST</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> helper(root, INT_MIN, INT_MAX);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="平衡二叉树"><a href="#平衡二叉树" class="headerlink" title="平衡二叉树"></a>平衡二叉树</h2><p>一棵树为平衡二叉树，当且仅当左右两个子树的高度差的绝对值不超过1，并且左右两个子树也是一颗平衡二叉树。</p>
<p>空树是一个平衡二叉树。</p>
<p>判断一棵树是否为平衡二叉树：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">level</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!root)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> max(level(root-&gt;left),level(root-&gt;right))+<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isBalanced</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!root)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">int</span> factor = <span class="built_in">abs</span>(level(root-&gt;left) - level(root-&gt;right));</span><br><span class="line">    <span class="keyword">return</span> factor &gt; <span class="number">2</span> ? <span class="literal">false</span> : isBalenced(root-&gt;left)&amp;&amp;isBalance(root-&gt;rihgt);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>上述方法中，level要多次重复计算。</p>
<p>可以采用动态规划来避免level的多次计算。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">isBalancedHelper</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == root)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> leftHeight = isBalancedHelper(root-&gt;left);</span><br><span class="line">    <span class="keyword">if</span> (leftHeight == <span class="number">-1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> rightHeight = isBalancedHelper(root-&gt;right);</span><br><span class="line">    <span class="keyword">if</span>(rightHeight == <span class="number">-1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">abs</span>(leftHeight - rightHeight) &gt; <span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> max(leftHeight, rightHeight) + <span class="number">1</span>;S</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isBalanced</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> isBalancedHelper(root) != <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="求二叉树中路径"><a href="#求二叉树中路径" class="headerlink" title="求二叉树中路径"></a>求二叉树中路径</h2><p>求取二叉树的所有路径中，和等于某个值的路径。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pathSumHelper</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; path, <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt;&amp; result, TreeNode* root, <span class="keyword">int</span> sum)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == root)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    path.push_back(root-&gt;val);</span><br><span class="line">    <span class="keyword">if</span>(sum == root-&gt;val)</span><br><span class="line">        result.push_back(path);</span><br><span class="line">    pathSumHelper(path, result, root-&gt;left, sum - root-&gt;val);</span><br><span class="line">    pathSumHelper(path, result, root-&gt;right, sum - root-&gt;val);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; pathSum(TreeNode* root, <span class="keyword">int</span> sum)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; path;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; result;</span><br><span class="line">    pathSumHelper(path, result, root, sum);</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>如果要求路径的尾部一定是叶子节点：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pathSumHelper</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; path, <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt;&amp; result, TreeNode* root, <span class="keyword">int</span> sum)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == root)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    path.push_back(root-&gt;val);</span><br><span class="line">    <span class="keyword">if</span>(sum == root-&gt;val &amp;&amp; <span class="literal">nullptr</span> == root-&gt;right &amp;&amp; <span class="literal">nullptr</span> == root-&gt;left);</span><br><span class="line">        result.push_back(path);</span><br><span class="line">    pathSumHelper(path, result, root-&gt;left, sum - root-&gt;val);</span><br><span class="line">    pathSumHelper(path, result, root-&gt;right, sum - root-&gt;val);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; pathSum(TreeNode* root, <span class="keyword">int</span> sum)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; path;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; result;</span><br><span class="line">    pathSumHelper(path, result, root, sum);</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="二叉搜索树的中序遍历的下一个元素"><a href="#二叉搜索树的中序遍历的下一个元素" class="headerlink" title="二叉搜索树的中序遍历的下一个元素"></a>二叉搜索树的中序遍历的下一个元素</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">leftMostNode</span><span class="params">(TreeNode* node)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!node)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">while</span>(<span class="literal">nullptr</span> != node-&gt;left)</span><br><span class="line">        node = node-&gt;left;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isLeftChild</span><span class="params">(TreeNode* node, TreeNode* parent)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> parent-&gt;left == node;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">TreeNode* <span class="title">inOrderSuccessor</span><span class="params">(TreeNode* node)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == node)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> != node-&gt;right)</span><br><span class="line">        <span class="keyword">return</span> leftMostNode(node-&gt;right);</span><br><span class="line">    TreeNode* parent = node-&gt;parent;</span><br><span class="line">    <span class="keyword">while</span>(parent &amp;&amp; !isLeftChild(node, parent))</span><br><span class="line">    &#123;</span><br><span class="line">        node = parent;</span><br><span class="line">        parent = node-&gt;parent;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> parent;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>如果节点没有父指针。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">leftMostNode</span><span class="params">(TreeNode* node)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!node)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">while</span>(<span class="literal">nullptr</span> != node-&gt;left)</span><br><span class="line">        node = node-&gt;left;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">TreeNode* <span class="title">inOrderSuccessor</span><span class="params">(TreeNode* node, TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!node)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">if</span>(!node-&gt;right)</span><br><span class="line">        <span class="keyword">return</span> leftMostNode(node-&gt;right);</span><br><span class="line">    TreeNode* successor = <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">while</span>(root)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(root-&gt;val &gt; node-&gt;val)</span><br><span class="line">        &#123;</span><br><span class="line">            successor = root;</span><br><span class="line">            root = root-&gt;left;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            root = root-&gt;right;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> successor;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="最近的公共节点"><a href="#最近的公共节点" class="headerlink" title="最近的公共节点"></a>最近的公共节点</h2><p><img src="C:\Users\zxp\AppData\Roaming\Typora\typora-user-images\1569322792414.png" alt="1569322792414"></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">lowestCommonAncestor</span><span class="params">(TreeNode* root, TreeNode* A, TreeNode* B)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> == root || root == A || root == B)</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    TreeNode* left = lowestCommonAncestor(root-&gt;left, A, B);</span><br><span class="line">    TreeNode* right = lowestCommonAncestor(root-&gt;right, A, B);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">nullptr</span> != left &amp;&amp; <span class="literal">nullptr</span> != right)</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> (<span class="literal">nullptr</span> != left) ? left : right;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="重构二叉树"><a href="#重构二叉树" class="headerlink" title="重构二叉树"></a>重构二叉树</h2><p>根据两个遍历序列来重构二叉树。</p>
<p>比如：根据先序遍历和中序遍历。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">rebuild</span><span class="params">(<span class="keyword">char</span> * pStr, <span class="keyword">char</span> *iStr, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(n &lt;= <span class="number">0</span>)   </span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    TreeNode* root = <span class="keyword">new</span> TreeNode;</span><br><span class="line">    root-&gt;data = *pStr;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">char</span> * iter;</span><br><span class="line">    <span class="keyword">for</span>(iter = iStr; iter &lt; iStr+n; ++iter)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(*iter== *pStr)</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> k = iter - iStr;</span><br><span class="line">    root-&gt;left = rebuild(pStr+<span class="number">1</span>, iStr, k);</span><br><span class="line">    root-&gt;right = rebuild(pStr+k+<span class="number">1</span>, iter+k, n-k<span class="number">-1</span>);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="之字形打印二叉树"><a href="#之字形打印二叉树" class="headerlink" title="之字形打印二叉树"></a>之字形打印二叉树</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val;</span></span><br><span class="line"><span class="comment">    struct TreeNode *left;</span></span><br><span class="line"><span class="comment">    struct TreeNode *right;</span></span><br><span class="line"><span class="comment">    TreeNode(int x) :</span></span><br><span class="line"><span class="comment">            val(x), left(NULL), right(NULL) &#123;</span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment">&#125;;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; Print(TreeNode* pRoot) &#123;</span><br><span class="line">        <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; result;</span><br><span class="line">        <span class="built_in">stack</span>&lt;TreeNode*&gt; sta1;</span><br><span class="line">        <span class="built_in">stack</span>&lt;TreeNode*&gt; sta2;</span><br><span class="line">        <span class="keyword">int</span> level = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span>(pRoot)</span><br><span class="line">        &#123;</span><br><span class="line">            sta1.push(pRoot);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(!sta1.empty() || !sta2.empty())</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; line;</span><br><span class="line">            <span class="keyword">int</span> n = sta1.empty() ? sta2.size() : sta1.size();</span><br><span class="line">            <span class="keyword">while</span>(n--)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span> (level % <span class="number">2</span> == <span class="number">1</span>)</span><br><span class="line">                &#123;</span><br><span class="line">                    TreeNode * temp = sta1.top();</span><br><span class="line">                    sta1.pop();</span><br><span class="line">                    line.push_back(temp-&gt;val);</span><br><span class="line">                    <span class="keyword">if</span>(temp-&gt;left)</span><br><span class="line">                        sta2.push(temp-&gt;left);</span><br><span class="line">                    <span class="keyword">if</span>(temp-&gt;right)</span><br><span class="line">                        sta2.push(temp-&gt;right);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span>&#123;</span><br><span class="line">                    TreeNode * temp = sta2.top();</span><br><span class="line">                    sta2.pop();</span><br><span class="line">                    line.push_back(temp-&gt;val);</span><br><span class="line">                    <span class="keyword">if</span>(temp-&gt;right)</span><br><span class="line">                        sta1.push(temp-&gt;right);</span><br><span class="line">                    <span class="keyword">if</span>(temp-&gt;left)</span><br><span class="line">                        sta1.push(temp-&gt;left);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            ++level;</span><br><span class="line">            result.push_back(line);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h1 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h1><h2 id="内排序"><a href="#内排序" class="headerlink" title="内排序"></a>内排序</h2><p>内排序是指所有的数据已经读入内存，在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时，内排序一般假定所有用到的辅助空间也可以直接存在于内存中。</p>
<p>另一类排序称作外排序，即存在中无法保存全部数据，需要进行磁盘访问，每次读入部分数据到内存进行排序。</p>
<ul>
<li>快速排序</li>
<li>归并排序</li>
<li>堆排序</li>
<li>桶排序和基数排序</li>
</ul>
<h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><p>将线性数据结构（如array，vector或list）分为两部分，对两部分分别进行排序，排序完成后，再将各自排序好的两个部分合并还原成一个有序数组。</p>
<p>由于归并排序不依赖于随机读写，因此具有很强的普适性，适用于list等数据结构。算法的时间复杂度O(nlongn)，需要额外O(n)空间。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge_sort</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> helper[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left &gt;= right)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> mid = right - (right - left)/<span class="number">2</span>;</span><br><span class="line">    merge_sort(<span class="built_in">array</span>, helper, left, mid);</span><br><span class="line">    merge_sort(<span class="built_in">array</span>, helper, mid+<span class="number">1</span>, right);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> helperLeft = left;</span><br><span class="line">    <span class="keyword">int</span> helperRight = mid + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> cur = left;</span><br><span class="line">    <span class="keyword">while</span>(helperLeft &lt;= mid &amp;&amp; helperRight &lt;= right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(helper[helperLeft] &gt; helper[helperRight])</span><br><span class="line">            <span class="built_in">array</span>[curr++] = helper[helperRight++];</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="built_in">array</span>[curr++] = helper[helperLeft++];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span>(helperLeft &lt;= mid)</span><br><span class="line">        <span class="built_in">array</span>[curr++] = helper[helperLeft++];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><p>快速排序是最为常用的排序算法，算法核心于归并排序类似，也采用“分而治之”的想法。</p>
<p>随机选定一个元素作为轴值，利用该轴值将数组分为左右两部分，左边的元素都比轴值小，右边元素都比轴值大，但他们不是安全排序的。在此基础上，分别对左右两部分分别递归调用快速排序，使得左右部分完全排序。</p>
<p>算法的平均时间复杂度是O(nlogn)，在最坏的情况为O(n^2)，额外空间复杂度O(longn)。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">partition</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pivot = <span class="built_in">array</span>[right];</span><br><span class="line">    <span class="keyword">while</span>(left != right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">while</span>(left &lt; right &amp;&amp; <span class="built_in">array</span>[left] &lt; pivot)</span><br><span class="line">            left++;</span><br><span class="line">        <span class="keyword">if</span>(left &lt; right)</span><br><span class="line">            swap(<span class="built_in">array</span>[left], <span class="built_in">array</span>[right--]);</span><br><span class="line">        <span class="keyword">while</span>(left &lt; right &amp;&amp; <span class="built_in">array</span>[right] &gt; pivot)</span><br><span class="line">            right--;</span><br><span class="line">        <span class="keyword">if</span>(left &lt; right)</span><br><span class="line">            swap(<span class="built_in">array</span>[left++], <span class="built_in">array</span>[right]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">array</span>[left] = pivot;</span><br><span class="line">    <span class="keyword">return</span> left;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">qSort</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left &gt;= right)</span><br><span class="line">    	<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> index = partition(<span class="built_in">array</span>, left, right);</span><br><span class="line">    qSort(<span class="built_in">array</span>, left, index<span class="number">-1</span>);</span><br><span class="line">    qSort(<span class="built_in">array</span>, index+<span class="number">1</span>, right);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">qSort</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    qSort(<span class="built_in">array</span>, <span class="number">0</span>, size<span class="number">-1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="快速选择排序"><a href="#快速选择排序" class="headerlink" title="快速选择排序"></a>快速选择排序</h3><p>快速选择算法能够在平均O(n)时间内从<strong>一个无序数组中返回第K大的元素。</strong></p>
<p>算法实际上利用了快速排序的思想，将数组依照一个轴值分割成两个部分，左边元素都比轴值小，右边元素都比轴值大。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">partition</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pivot = <span class="built_in">array</span>[right];</span><br><span class="line">    <span class="keyword">while</span>(left != right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">while</span>(left &lt; right &amp;&amp; <span class="built_in">array</span>[left] &lt; pivot)</span><br><span class="line">            left++;</span><br><span class="line">        <span class="keyword">if</span>(left &lt; right)</span><br><span class="line">            swap(<span class="built_in">array</span>[left], <span class="built_in">array</span>[right--]);</span><br><span class="line">        <span class="keyword">while</span>(left &lt; right &amp;&amp; <span class="built_in">array</span>[right] &gt; pivot)</span><br><span class="line">            right--;</span><br><span class="line">        <span class="keyword">if</span>(left &lt; right)</span><br><span class="line">            swap(<span class="built_in">array</span>[left++], <span class="built_in">array</span>[right]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">array</span>[left] = pivot;</span><br><span class="line">    <span class="keyword">return</span> left;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">quik_select</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left &gt;= right)</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">array</span>[left];</span><br><span class="line">    <span class="keyword">int</span> index = partition(<span class="built_in">array</span>, left, right);</span><br><span class="line">    <span class="keyword">int</span> size = index - left + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(size == k)</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">array</span>[left+k<span class="number">-1</span>];</span><br><span class="line">    <span class="keyword">else</span>(size &gt; k)</span><br><span class="line">        <span class="keyword">return</span> quik_select(<span class="built_in">array</span>, left, index<span class="number">-1</span>, k);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> quik_select(<span class="built_in">array</span>, index+<span class="number">1</span>, right, k-size);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h3><p>桶排序不需要进行数据之间的两两比较，但是需要事先直到数组的一些具体情况。</p>
<p>特别地，桶排序适用于知道待排序数组大小范围的情况。其特性在于将数据根据其大小，放入合适的“桶（容器）”中，再依次从桶中取出，形成有序序列。</p>
<p>时间复杂度：O(max+n), 空间复杂度O(n+max)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">BucketSort</span><span class="params">(<span class="keyword">int</span> <span class="built_in">array</span>[], <span class="keyword">int</span> n, <span class="keyword">int</span> max)</span> <span class="comment">//max为array中数的最大值</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> tempArray[n];</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        tempArray[i] = <span class="built_in">array</span>[i];</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> count[max]; <span class="comment">//桶</span></span><br><span class="line">    <span class="built_in">memset</span>(count, <span class="number">0</span>, max * <span class="keyword">sizeof</span>(<span class="keyword">int</span>));</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        count[<span class="built_in">array</span>[i]]++;</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">1</span>; i &lt; max; i++)</span><br><span class="line">        count[i] = count[i<span class="number">-1</span>]+count[i];</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        <span class="built_in">array</span>[--count[tempArray[i]]] = tempArray[i];</span><br><span class="line">    </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">RadixSort</span><span class="params">(<span class="keyword">int</span> Array[], <span class="keyword">int</span> n, <span class="keyword">int</span> digits, <span class="keyword">int</span> radix)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> *TempArray = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">int</span> * count = <span class="keyword">new</span> <span class="keyword">int</span>[radix];</span><br><span class="line">    <span class="keyword">int</span> i, j, k;</span><br><span class="line">    <span class="keyword">int</span> Radix = <span class="number">1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">1</span>; i &lt;= digits; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (j = <span class="number">0</span>; j &lt; radix; j++)</span><br><span class="line">            count[j] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (j = <span class="number">0</span>; j &lt; n; j++)</span><br><span class="line">        &#123;</span><br><span class="line">            k = (Array[j] / Radix) % radix;</span><br><span class="line">            count[k]++;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span>(j = <span class="number">1</span>; j &lt; radix; j++)</span><br><span class="line">            count[i] = count[i<span class="number">-1</span>] + count[i];</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span> (j = n - <span class="number">1</span>; j &gt;= <span class="number">0</span>; j--)</span><br><span class="line">        &#123;</span><br><span class="line">            k = (Array[j] / Radix) % radix;</span><br><span class="line">            count[k]--;</span><br><span class="line">            TempArray[count[k]] = Array[j];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (j = <span class="number">0</span>; j &lt; n; ++j)</span><br><span class="line">            Array[j] = TempArray[j];</span><br><span class="line">        Radix *= radix;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">delete</span> [] TempArray;</span><br><span class="line">    <span class="keyword">delete</span> [] count;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="外排序"><a href="#外排序" class="headerlink" title="外排序"></a>外排序</h2><p>假设文件需要分成k块读入，需要从小到达进行排序：</p>
<ul>
<li>依次读入每个文件快，在内存中对当前文件块进行排序（应用恰当的内排序算法）。此时，每块文件相等于一个由小到大排列的有序队列。</li>
<li>在内存中建立一个最小值堆，读入每块文件的队列头</li>
<li>弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组</li>
<li>当临时数组存满，将数组写至磁盘，并清空数组内容。</li>
<li>重复第3、4步，直到所有文件块读取完毕。</li>
</ul>
<h2 id="堆和堆排序"><a href="#堆和堆排序" class="headerlink" title="堆和堆排序"></a>堆和堆排序</h2><p>根节点元素比它的所有子节点都要大。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925144546.png" alt=""></p>
<ul>
<li>堆能够很方便地维护动态数据的最大值、最小值或中位数(需要两个堆)。</li>
<li>优先队列相比简单的queue更适用于需要优先级的情景</li>
<li>与queue类似，该结构适合push和pop，但不方便update和检索。</li>
</ul>
<h3 id="堆实现"><a href="#堆实现" class="headerlink" title="堆实现"></a>堆实现</h3><p>堆的底部实现是一个动态数组。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925144947.png" alt=""></p>
<h3 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h3><p>堆排序利用了堆作为逻辑存储结果，将输入array变成一个最大值堆，然后，我们反复进行堆的弹出操作。</p>
<p>时间复杂度O(nlogn)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">downHeap</span><span class="params">(<span class="keyword">int</span> a[], <span class="keyword">int</span> N, <span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> j, v;</span><br><span class="line">    v = a[k];</span><br><span class="line">    <span class="keyword">while</span> (k &lt;= N/<span class="number">2</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        j = K + k;</span><br><span class="line">        <span class="keyword">if</span> (j &lt; k &amp;&amp; a[j] &lt; a[j+<span class="number">1</span>]) j++;</span><br><span class="line">        <span class="keyword">if</span> (v &gt;= a[j]) <span class="keyword">break</span>;</span><br><span class="line">        a[k] = a[j]; </span><br><span class="line">        k = j;</span><br><span class="line">    &#125;</span><br><span class="line">    a[k] = v;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">heapSort</span><span class="params">(<span class="keyword">int</span> a[], <span class="keyword">int</span> N)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> k , t;</span><br><span class="line">    <span class="keyword">for</span> (k = N/<span class="number">2</span>; k&gt;=<span class="number">1</span>; --k)</span><br><span class="line">        downHeap(a, N, k);</span><br><span class="line">    <span class="keyword">while</span>(N &gt; <span class="number">1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        t = a[<span class="number">1</span>];</span><br><span class="line">        a[<span class="number">1</span>] = a[N];</span><br><span class="line">        a[N] = t;</span><br><span class="line">        downHeap(a, --N, <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="c-中堆和优先级队列"><a href="#c-中堆和优先级队列" class="headerlink" title="c++中堆和优先级队列"></a>c++中堆和优先级队列</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">priority_queue&lt;<span class="keyword">int</span>&gt; myPriorityQueue;</span><br><span class="line">myPriorityQueue.push(<span class="number">30</span>);</span><br><span class="line">myPriorityQueue.push(<span class="number">20</span>);</span><br><span class="line">myPriorityQueue.push(<span class="number">50</span>);</span><br><span class="line">myPriorityQueue.push(<span class="number">40</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(!myPriorityQueue.empty())</span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">' '</span> &lt;&lt; myPriorityQueue.top();</span><br><span class="line">    myPriorityQueue.pop();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//输出： 50 40 30 20</span></span><br></pre></td></tr></table></figure>
<p>当题目中出现“前k个”，“合并/排序k组数据”或者“数据流（即不知道全部数据，而是每次读入一个）”时，可以考虑使用heap，动态地维护最大值/最小值信息。 </p>
<h1 id="二分搜索"><a href="#二分搜索" class="headerlink" title="二分搜索"></a>二分搜索</h1><p>递归实现：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>* <span class="built_in">array</span>, <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">int</span> value)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left &gt; right)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">int</span> mid = left + (right - left) / <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">array</span>[mid] == value)</span><br><span class="line">        <span class="keyword">return</span> mid;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">array</span>[mid] &gt; value)</span><br><span class="line">        <span class="keyword">return</span> binarySearch(<span class="built_in">array</span>, left, mid<span class="number">-1</span>, value);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> binarySearch(<span class="built_in">array</span>, mid+<span class="number">1</span>, right, value);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>循环实现：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span>* <span class="built_in">array</span>, <span class="keyword">const</span> <span class="keyword">int</span> size, <span class="keyword">const</span> <span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> right = size<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (val == <span class="built_in">array</span>[mid])</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">array</span>[mid] &gt; val)</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            left = mid + <span class="number">1</span>;   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>对于<strong>有序或者部分有序容器</strong>的搜索：二分查找或其变种基本上都是最佳的方法。</p>
<h2 id="数组中下标等于对应元素值"><a href="#数组中下标等于对应元素值" class="headerlink" title="数组中下标等于对应元素值"></a>数组中下标等于对应元素值</h2><p>从一个有序数组中，找到其值等于下标值的元素：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findValueEqualIndex</span><span class="params">(<span class="keyword">int</span>* <span class="built_in">array</span>, <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> right = size - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) &gt;&gt; <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span> (mid == <span class="built_in">array</span>[mid])</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(mid &lt; <span class="built_in">array</span>[mide])</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="寻找峰值"><a href="#寻找峰值" class="headerlink" title="寻找峰值"></a>寻找峰值</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925184730.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//[1,2,1,3,4,5,7,6]  //峰值有2，7</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findPeakHelper</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span>* <span class="built_in">array</span>, <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> mid = left + (right - left)/<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span> ((mid == <span class="number">0</span> || <span class="built_in">array</span>[mid<span class="number">-1</span>] &lt;= <span class="built_in">array</span>[mid]) &amp;&amp;</span><br><span class="line">       (mid == n<span class="number">-1</span> || <span class="built_in">array</span>[mide+<span class="number">1</span>] &lt;= <span class="built_in">array</span>[mid]))</span><br><span class="line">        <span class="keyword">return</span> mid;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (mid &gt; <span class="number">0</span> &amp;&amp; <span class="built_in">array</span>[mid<span class="number">-1</span>] &gt; <span class="built_in">array</span>[mid])</span><br><span class="line">        <span class="keyword">return</span> findPeakHelper(<span class="built_in">array</span>, left, mid<span class="number">-1</span>, n);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> findPeakHelper(<span class="built_in">array</span>, mid+<span class="number">1</span>, right, n);</span><br><span class="line">&#125; </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findPeak</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> * <span class="built_in">array</span>, <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> findPeakHelper(<span class="built_in">array</span>, <span class="number">0</span>, size<span class="number">-1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="旋转有序数组中查找"><a href="#旋转有序数组中查找" class="headerlink" title="旋转有序数组中查找"></a>旋转有序数组中查找</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925193310.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findElementInArrayHelper</span><span class="params">(<span class="keyword">int</span>* <span class="built_in">array</span>, <span class="keyword">int</span> low, <span class="keyword">int</span> high <span class="keyword">int</span> target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left &gt; right)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">int</span> mid = low + (higt - low) / <span class="number">2</span>;</span><br><span class="line">   	<span class="keyword">if</span> (<span class="built_in">array</span>[mid] == target)</span><br><span class="line">        <span class="keyword">return</span> mid;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">array</span>[low] &lt;= <span class="built_in">array</span>[mid])</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (target &gt;= <span class="built_in">array</span>[low] &amp;&amp; target &lt;= <span class="built_in">array</span>[mid])</span><br><span class="line">            <span class="keyword">return</span> findElementInArrayHelper(<span class="built_in">array</span>, low, mid<span class="number">-1</span>, target);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="keyword">return</span> findElementInArrayHelper(<span class="built_in">array</span>, mid+<span class="number">1</span>, high, target);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (target &gt;= <span class="built_in">array</span>[mid] &amp;&amp; target &lt;= <span class="built_in">array</span>[higt])</span><br><span class="line">            <span class="keyword">return</span> findElementInArrayHelper(<span class="built_in">array</span>, mid+<span class="number">1</span>, high, target);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="keyword">return</span> findElementInArrayHelper(<span class="built_in">array</span>, low, mid<span class="number">-1</span>, target);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findElementInArray</span><span class="params">(<span class="keyword">int</span> * <span class="built_in">array</span>, <span class="keyword">int</span> size, <span class="keyword">int</span> target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> findElementInArrayHelper(<span class="built_in">array</span>, <span class="number">0</span>, size<span class="number">-1</span>, target);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>循环实现：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findElementInArray</span><span class="params">(<span class="keyword">int</span> * <span class="built_in">array</span>, <span class="keyword">int</span> size, <span class="keyword">int</span> target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> low = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> high = size - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(low &lt;= high)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = low + (high - low) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (target == <span class="built_in">array</span>[mid])</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">array</span>[low] &lt;= <span class="built_in">array</span>[mid])</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">array</span>[low] &lt;= target &amp;&amp; target &lt;= <span class="built_in">array</span>[mid])</span><br><span class="line">                high = mid - <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                low = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">array</span>[mid] &lt;= target &amp;&amp; target &lt;= <span class="built_in">array</span>[higt])</span><br><span class="line">                low = mid + <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                high = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="范围搜索"><a href="#范围搜索" class="headerlink" title="范围搜索"></a>范围搜索</h2><p>对于排序好的数组中，存在重复元素。找出某个元素的起始位置和结束位置。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">searchRangeHelper</span><span class="params">(<span class="keyword">int</span> A[], <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">int</span> target, <span class="keyword">int</span> begin, <span class="keyword">int</span> end)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left &gt; right)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> mid = left + (right - left) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(A[mid] == target)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (mid &lt; begin || begin == <span class="number">-1</span>)</span><br><span class="line">            begin = mid;</span><br><span class="line">        <span class="keyword">if</span> (mid &gt; end || end == <span class="number">-1</span>)</span><br><span class="line">            end = mid</span><br><span class="line">        searchRangeHelper(A, left, mid<span class="number">-1</span>, target, begin, end);</span><br><span class="line">        searchRangeHleper(A, mid+<span class="number">1</span>, right, target, begin, end);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (A[mid] &lt; target)</span><br><span class="line">        searchRangeHelper(A, mid + <span class="number">1</span>, right, target, begin, end);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        searchRangeHelper(A, left, mid - <span class="number">1</span>, target, begin, end);</span><br><span class="line">        </span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; searchRange(<span class="keyword">int</span> A[], <span class="keyword">int</span> n, <span class="keyword">int</span> target)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">int</span> begin = <span class="number">-1</span>, end = <span class="number">-1</span>;</span><br><span class="line">    searchRangeHelper(A, <span class="number">0</span>, n<span class="number">-1</span>,target, begin, end);</span><br><span class="line">    </span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">    res.push_back(begin);</span><br><span class="line">    res.push_back(end);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="矩阵查找"><a href="#矩阵查找" class="headerlink" title="矩阵查找"></a>矩阵查找</h2><p>一个M×N的矩阵，每一行、每一列都是排序的。</p>
<p>判断一个元素是否在该矩阵中。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925200822.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">searchMatrixHelper</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; Matrix, <span class="keyword">int</span> target, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; res)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> row = Matrix.size();</span><br><span class="line">    <span class="keyword">if</span> (row == <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">int</span> column = Matrix[<span class="number">0</span>].size();</span><br><span class="line">    <span class="keyword">int</span> j = column - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>; </span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; row &amp;&amp; j &gt;= <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (Matrix[i][j] == target)</span><br><span class="line">        &#123;</span><br><span class="line">            res.push_back(i);</span><br><span class="line">            res.push_back(j);</span><br><span class="line">            <span class="keyword">return</span> res;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (Matrix[i][j] &gt; target)</span><br><span class="line">            --j;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            i++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; searchMatrix(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; Matrix, <span class="keyword">int</span> target) </span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">    searchMatrixHelper(Matrix, target, res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="搜索矩阵"><a href="#搜索矩阵" class="headerlink" title="搜索矩阵"></a>搜索矩阵</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190925202734.png" alt=""></p>
<p>首先通过判断最后一列，来判断元素在哪一行，然后在对应进行二分查找。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">binarySearch</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="built_in">array</span>, <span class="keyword">const</span> <span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> right = <span class="built_in">array</span>.size()<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (val == <span class="built_in">array</span>[mid])</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">array</span>[mid] &gt; val)</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            left = mid + <span class="number">1</span>;   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">searchMatrix</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; Matrix, <span class="keyword">int</span> target)</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> row = Matrix.size();</span><br><span class="line">    <span class="keyword">if</span> (row &lt;= <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">int</span> column = Matrix[<span class="number">0</span>].size();</span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>, j = column<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; n &amp;&amp; j &gt;= <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (Matrix[i][j] == target)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (Matrix[i][j] &lt; target)</span><br><span class="line">            i++;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">return</span> binarySearch(Matirx[i], target);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>另一种思路就是将整个二维数组看作是一个一维数组。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">searchMatrix</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; Matrix, <span class="keyword">int</span> target)</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> row = Matrix.size();</span><br><span class="line">    <span class="keyword">if</span> (row &lt;= <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">int</span> column = Matrix[<span class="number">0</span>].size();</span><br><span class="line">    <span class="keyword">int</span> right = row * column<span class="number">-1</span>;</span><br><span class="line"> 	<span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (Matrix[mid/column][mid%column] == target)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (Matrix[mid/column][mid%column] &lt; target)</span><br><span class="line">            right = mid + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        	left = mid - <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="求平方根"><a href="#求平方根" class="headerlink" title="求平方根"></a>求平方根</h2><p>即实现sqrt(x)，注意是整数，还是浮点数</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">double</span> precision = <span class="number">0.00001</span>;</span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">mySqrtHelper</span><span class="params">(<span class="keyword">double</span> x, <span class="keyword">double</span> lowBound, <span class="keyword">double</span> highBound)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">double</span> <span class="built_in">sqrt</span> = lowBound / <span class="number">2</span> + highBound /<span class="number">2</span> ;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">abs</span>(<span class="built_in">sqrt</span> * <span class="built_in">sqrt</span> - x) &lt; precision)</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">sqrt</span>;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">sqrt</span> * <span class="built_in">sqrt</span> - x &gt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> mySqrtHelper(x, lowBound, <span class="built_in">sqrt</span>);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> mySqrtHelper(x, <span class="built_in">sqrt</span>, highBound);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">mySqrt</span><span class="params">(<span class="keyword">double</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x &lt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span> (x &lt; <span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> mySqrtHelper(x, x, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    	<span class="keyword">return</span> mySqrtHelper(x, <span class="number">1</span>, x);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>牛顿迭代法，迭代的速度更快。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">float</span> <span class="title">sqareRoot</span><span class="params">(<span class="keyword">float</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">float</span> x = n;</span><br><span class="line">    <span class="keyword">float</span> y = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">float</span> e = <span class="number">0.000001</span>;</span><br><span class="line">    <span class="keyword">while</span> (x - y &gt; e)&#123;</span><br><span class="line">        x = (x + y)/<span class="number">2</span>;</span><br><span class="line">        y = n/x;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="最新的请求"><a href="#最新的请求" class="headerlink" title="最新的请求"></a>最新的请求</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927202113.png" alt=""></p>
<h2 id="人的年龄排序"><a href="#人的年龄排序" class="headerlink" title="人的年龄排序"></a>人的年龄排序</h2><p>对于人的数量比较大时，根据人的年龄排序，利用桶排序的效率比较高。</p>
<h1 id="大规模和内存有限的问题"><a href="#大规模和内存有限的问题" class="headerlink" title="大规模和内存有限的问题"></a>大规模和内存有限的问题</h1><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927203057.png" alt=""></p>
<h2 id="社交网络"><a href="#社交网络" class="headerlink" title="社交网络"></a>社交网络</h2><p>针对一个非常大的社交网络，设计一个数据结构和一个算法    来表示两个人之间的关系。</p>
<h2 id="检测重复元素"><a href="#检测重复元素" class="headerlink" title="检测重复元素"></a>检测重复元素</h2><p>给定一个非常大的URL集合，比如：10亿。设计一个算法来检测重复的URL。</p>
<h2 id="实现表的合并"><a href="#实现表的合并" class="headerlink" title="实现表的合并"></a>实现表的合并</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190927210719.png" alt=""></p>
<p>2）将一个表存入到hash表中。然后遍历另一个表，</p>
<p>3）将两个表都做一个hash运算，有相同的hash的student_id放到同一机器上，然后利用2）的方法对每台机器进行合并</p>
<h1 id="动态规划和递归"><a href="#动态规划和递归" class="headerlink" title="动态规划和递归"></a>动态规划和递归</h1><p>相同点：都能分解成若干子问题</p>
<p>不同点：DP存储子问题结果</p>
<p>动态规划避免子问题的重复计算，通过数组来记录每个子问题的解，达到空间换时间。</p>
<p>动态规划四要素：</p>
<ul>
<li>状态：存储小规模问题的结果</li>
<li>方程：从小状态到大状态的转移</li>
<li>初始化：最极限的小状态</li>
<li>答案：最大的那个状态</li>
</ul>
<h1 id="记忆化搜索"><a href="#记忆化搜索" class="headerlink" title="记忆化搜索"></a>记忆化搜索</h1><p>在递归过程中，通过一个hashtable记录中间的计算结果，比如input作为key，output作为value。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">T <span class="title">func</span><span class="params">(N node, HastTable&lt;N,T&gt;&amp; cache)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (cache.contains(node))</span><br><span class="line">        <span class="keyword">return</span> cache.get(node);</span><br><span class="line">    ... </span><br><span class="line">    T sub_res = func(next_node, cache);\</span><br><span class="line">    ...</span><br><span class="line">        <span class="comment">//当前子问题的解，依赖于更小的子问题</span></span><br><span class="line">    T res = G(sub_res...);</span><br><span class="line">    cache.<span class="built_in">set</span>(node, ers);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="算法策略比较"><a href="#算法策略比较" class="headerlink" title="算法策略比较"></a>算法策略比较</h1><ul>
<li>分而治之：归并排序，快速排序</li>
<li>动态规划：记录子问题的结果，避免不重复计算子问题</li>
<li>贪婪算法：记录走向全局最优解的局部解，当计算后续解是可以考虑前面的局部解，比如迪杰斯特拉算法</li>
<li>回溯：穷举，树的DFS</li>
</ul>
<p>fibonacci数列实现：</p>
<ul>
<li><p>递归</p>
</li>
<li><p>动态规划</p>
</li>
<li>矩阵乘法：[[1,1],[1,0]]相乘</li>
<li>c++模板</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Fib</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">enum</span>&#123;</span><br><span class="line">    	val = Fib&lt;N<span class="number">-1</span>&gt;::val + Fib&lt;N<span class="number">-2</span>&gt;::val  </span><br><span class="line">    &#125;;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span>&lt;&gt;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Fib</span>&lt;0&gt;</span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">enum</span>&#123;</span><br><span class="line">		val = <span class="number">0</span></span><br><span class="line">	&#125;;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span>&lt;&gt;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Fib</span>&lt;1&gt;</span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">enum</span>&#123;</span><br><span class="line">		val = <span class="number">1</span>;</span><br><span class="line">	&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="爬楼梯"><a href="#爬楼梯" class="headerlink" title="爬楼梯"></a>爬楼梯</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">climibStairs</span><span class="params">(<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">2</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span> dp[n+<span class="number">1</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    dp[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">    dp[<span class="number">2</span>] = <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">3</span>; i &lt;= n; ++i)</span><br><span class="line">        dp[i] =  dp[i<span class="number">-1</span>] + dp[i<span class="number">-2</span>];</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="第n个素数"><a href="#第n个素数" class="headerlink" title="第n个素数"></a>第n个素数</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">GetNthPrime</span><span class="params">(<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">list</span>&lt;<span class="keyword">int</span>&gt; primes(<span class="number">1</span>,<span class="number">2</span>);</span><br><span class="line">    <span class="keyword">int</span> number = <span class="number">3</span>;</span><br><span class="line">    <span class="keyword">while</span>(primes.size() &lt;= n)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">bool</span> isPrime = <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> ite = primes.begin(); ite != primes.end() &amp;&amp; (*ite)*(*ite) &lt;= number; ++ite)</span><br><span class="line">            <span class="keyword">if</span> (number % *ite == <span class="number">0</span>)</span><br><span class="line">                isPrime = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">if</span> (isPrime)</span><br><span class="line">            primes.push_back(number);</span><br><span class="line">        number += <span class="number">2</span>;   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> *(primes.rbegin());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="分割单词"><a href="#分割单词" class="headerlink" title="分割单词"></a>分割单词</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20190930133603.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">wordBreak</span><span class="params">(<span class="built_in">string</span> s, <span class="built_in">unordered_set</span>&lt;<span class="built_in">string</span>&gt;&amp; dict)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> begin = <span class="number">0</span>, end = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">string</span> word;</span><br><span class="line">    <span class="keyword">bool</span> words[s.size()+<span class="number">1</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    words[<span class="number">0</span>] = <span class="literal">true</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; s.size() + <span class="number">1</span>; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        words[i] = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">for</span> (end = <span class="number">0</span>; end &lt; s.size(); ++end)</span><br><span class="line">            <span class="keyword">for</span> (begin = <span class="number">0</span>; begin &lt; end; ++begin)</span><br><span class="line">                <span class="keyword">if</span> (words[begin] &amp;&amp; dict.find(s.substr(begin, end-begin+<span class="number">1</span>))!= dict.end())</span><br><span class="line">                &#123;</span><br><span class="line">                    words[end+<span class="number">1</span>] = <span class="literal">true</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> words[s.size()];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="回文切割-Palindrome-Partition"><a href="#回文切割-Palindrome-Partition" class="headerlink" title="回文切割(Palindrome Partition)"></a>回文切割(Palindrome Partition)</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002152730.png" alt=""></p>
<h2 id="唯一的路径"><a href="#唯一的路径" class="headerlink" title="唯一的路径"></a>唯一的路径</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002153607.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">uniquePathsBackTrack</span><span class="params">(<span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (m == <span class="number">1</span> || n == <span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> uniquePath(m<span class="number">-1</span>, n) + uniquePath(m, n<span class="number">-1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">uniquePath</span><span class="params">(<span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   	<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; table(m, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;(n, <span class="number">1</span>));</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; m; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; ++j)</span><br><span class="line">            table[i][j] = table[i][j<span class="number">-1</span>] + table[i<span class="number">-1</span>][j];</span><br><span class="line">    <span class="keyword">return</span> table[m<span class="number">-1</span>][n<span class="number">-1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>节省空间通过一个一维数组实现：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">uniquePaths2</span><span class="params">(<span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; table(n, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; m; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; j++)</span><br><span class="line">            table[j] += table[j<span class="number">-1</span>];</span><br><span class="line">    <span class="keyword">return</span> table[n<span class="number">-1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="唯一路径Ⅱ"><a href="#唯一路径Ⅱ" class="headerlink" title="唯一路径Ⅱ"></a>唯一路径Ⅱ</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002154655.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">uniquePathsWithObstacles</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; &amp; obstacleGrid)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (obstacleGrid.empty() || obstacleGrid[<span class="number">0</span>].empty())</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> m = obstacleGrid.size();</span><br><span class="line">    <span class="keyword">int</span> n = obstacleGrid[<span class="number">0</span>].size();</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> dp[m][n];</span><br><span class="line">    dp[<span class="number">0</span>][<span class="number">0</span>] = (obstacleGrid[<span class="number">0</span>][<span class="number">0</span>] == <span class="number">1</span>) ? <span class="number">0</span> : <span class="number">1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; m; ++i)</span><br><span class="line">        dp[i][<span class="number">0</span>] = (dp[i<span class="number">-1</span>][<span class="number">0</span>] == <span class="number">1</span> &amp;&amp; obstacleGrid[i][<span class="number">0</span>] == <span class="number">0</span>) ? <span class="number">1</span> : <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; ++i)</span><br><span class="line">        dp[<span class="number">0</span>][j] = (dp[<span class="number">0</span>][j<span class="number">-1</span>] == <span class="number">1</span> &amp;&amp; obstacleGrid[<span class="number">0</span>][j] == <span class="number">0</span>) ? <span class="number">1</span> : <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; m; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; ++j)</span><br><span class="line">            <span class="keyword">if</span> (obstacleGrid[i][j] == <span class="number">1</span>)</span><br><span class="line">                dp[i][j] = <span class="number">0</span>;</span><br><span class="line">    		<span class="keyword">else</span></span><br><span class="line">                dp[i][j] = dp[i<span class="number">-1</span>][j] + dp[i][j<span class="number">-1</span>];</span><br><span class="line">    <span class="keyword">return</span> dp[m<span class="number">-1</span>][n<span class="number">-1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="最小的路径和"><a href="#最小的路径和" class="headerlink" title="最小的路径和"></a>最小的路径和</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002155621.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">minPathsum</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; &amp;grid)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (grid.empty() || grid[<span class="number">0</span>].empty())</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> row = grid.size();</span><br><span class="line">    <span class="keyword">int</span> col = grid[<span class="number">0</span>].size();</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> dp[row][col];</span><br><span class="line">    dp[<span class="number">0</span>][<span class="number">0</span>] = grid[<span class="number">0</span>][<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; row; ++i)</span><br><span class="line">        dp[i][<span class="number">0</span>] = dp[i<span class="number">-1</span>][<span class="number">0</span>] + grid[i][<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; col; ++j)</span><br><span class="line">        dp[<span class="number">0</span>][j] = dp[<span class="number">0</span>][j<span class="number">-1</span>] + grid[j][<span class="number">0</span>];</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; row; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; col; ++i)</span><br><span class="line">            dp[i][j] = min(dp[i][j<span class="number">-1</span>], dp[i<span class="number">-1</span>][j]) + grid[i][j];</span><br><span class="line">    <span class="keyword">return</span> dp[row<span class="number">-1</span>][col<span class="number">-1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="跳跃游戏"><a href="#跳跃游戏" class="headerlink" title="跳跃游戏"></a>跳跃游戏</h2><p><img src="C:\Users\zxp\AppData\Roaming\Typora\typora-user-images\1570003668165.png" alt="1570003668165"></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">canJump</span><span class="params">(<span class="keyword">int</span> A[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">int</span> v = A[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        v--;</span><br><span class="line">        <span class="keyword">if</span> ( v &lt; <span class="number">0</span> )</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">if</span> (v &lt; A[i]);</span><br><span class="line">        	v = A[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="三角形最小值"><a href="#三角形最小值" class="headerlink" title="三角形最小值"></a>三角形最小值</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002161222.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">minmumTotal</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; &amp;triangle)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> row = triangle.size();</span><br><span class="line">    <span class="keyword">if</span> (row == <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; total(row, INT_MAX);</span><br><span class="line">    total[<span class="number">0</span>] = triangle[<span class="number">0</span>][<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">int</span> minTotal = INT_MAX:</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; row; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &gt;= <span class="number">0</span>; --j)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (j == <span class="number">0</span>)</span><br><span class="line">                total[j] = total[j] + triangle[i][j];</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                total[j] = min(total[j<span class="number">-1</span>], total[j]) + triangle[i][j];</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; row; i++)</span><br><span class="line">        minTotal = min(minTotal, total[i]);</span><br><span class="line">    <span class="keyword">return</span> minTotal;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="唯一二叉搜索树"><a href="#唯一二叉搜索树" class="headerlink" title="唯一二叉搜索树"></a>唯一二叉搜索树</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002162550.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">numTrees</span><span class="params">(<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; dp(n+<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">    </span><br><span class="line">    dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    dp[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++)</span><br><span class="line">            dp[i] += dp[j] * dp[i-j<span class="number">-1</span>];</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h2 id="硬币置换"><a href="#硬币置换" class="headerlink" title="硬币置换"></a>硬币置换</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002212043.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">countWays</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; S, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; table(n+<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">    table[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; m; ++j)</span><br><span class="line">            table[i] += (i - S[j] &gt;= <span class="number">0</span>) ? table[i-S[j]] : <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> table[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>使用最少的硬币进行置换：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191002212847.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">countWays</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; S, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; table(n+<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">    table[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; m; ++j)</span><br><span class="line">            <span class="keyword">if</span> (i &gt;= S[j] &amp;&amp; table[i] &gt; table[i-S[j]])</span><br><span class="line">            	table[i] = table[i-S[j]] + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> table[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="最长子序列问题"><a href="#最长子序列问题" class="headerlink" title="最长子序列问题"></a>最长子序列问题</h1><h2 id="最长子序列"><a href="#最长子序列" class="headerlink" title="最长子序列"></a>最长子序列</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003085016.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">longestIncreasingSubsequence</span><span class="params">(<span class="keyword">int</span> arr[], <span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; maxLength(n, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">int</span> global_max = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; ++j)</span><br><span class="line">            <span class="keyword">if</span> (arr[i] &gt; arr[j] &amp;&amp; maxLength[j] + <span class="number">1</span> &gt; maxLength[i])</span><br><span class="line">                maxLenght[i] = maxLength[j] + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        <span class="keyword">if</span> (global_max &lt; maxLength[i])</span><br><span class="line">            global_max = maxLength[i];</span><br><span class="line">    <span class="keyword">return</span> global_max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="加油站"><a href="#加油站" class="headerlink" title="加油站"></a>加油站</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003085706.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">canCompleteCircuit</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; gas, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; cost)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> size = gas.size();</span><br><span class="line">    <span class="keyword">int</span> subSum = <span class="number">0</span>, sum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> <span class="built_in">array</span>[size];</span><br><span class="line">    <span class="keyword">int</span> index = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span>  i = <span class="number">0</span> ; i &lt; size; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">array</span>[i] = gas[i] - cost[i];</span><br><span class="line">        sum += <span class="built_in">array</span>[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (sum &lt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; size; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        subSum += <span class="built_in">array</span>[i];</span><br><span class="line">        <span class="keyword">if</span> (subSum &lt; <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            subSum = <span class="number">0</span>;</span><br><span class="line">            index = i+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="最长公共子序列"><a href="#最长公共子序列" class="headerlink" title="最长公共子序列"></a>最长公共子序列</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003090329.png" alt=""></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003090356.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lcs</span><span class="params">(<span class="built_in">string</span> str1, <span class="built_in">string</span> str2)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; lenght(str.size()+<span class="number">1</span>, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;(str.size()+<span class="number">1</span>));</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i= <span class="number">0</span>; i &lt; str1.size(); ++i)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; str2.size(); ++j)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (i == <span class="number">0</span> || j == <span class="number">0</span>)</span><br><span class="line">                lenght[i][j] = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (str[i<span class="number">-1</span>] ==  str2[j<span class="number">-1</span>])</span><br><span class="line">                length[i][j] = length[i<span class="number">-1</span>][j<span class="number">-1</span>] + <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> </span><br><span class="line">                length[i][j] = max(length[i<span class="number">-1</span>][j], length[i][j<span class="number">-1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="keyword">return</span> length[str1.size()][str2.size()];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="除本身之外的乘积"><a href="#除本身之外的乘积" class="headerlink" title="除本身之外的乘积"></a>除本身之外的乘积</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003091645.png" alt=""></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003091810.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">replaceWithProducts</span><span class="params">(<span class="keyword">int</span> elements[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> a[n];</span><br><span class="line">    <span class="keyword">int</span> products_below[n];</span><br><span class="line">    <span class="keyword">int</span> p = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span> ; i &lt; n; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        products_below[i] = p;</span><br><span class="line">        p *= elements[i];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> products_above[n];</span><br><span class="line">    p = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n<span class="number">-1</span>; i &gt;= <span class="number">0</span>; --i)</span><br><span class="line">    &#123;</span><br><span class="line">        products_above[i] = p;</span><br><span class="line">        p *= elements[i];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> products[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">        products[i] = products_below[i] * products_above[i];</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//第二种方法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">replaceWithProducts</span><span class="params">(<span class="keyword">int</span> elements[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> product = <span class="number">1</span>;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; table(n,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        table[i] = product;</span><br><span class="line">        product *= elements[i];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    product = <span class="number">1</span>;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res(n,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n<span class="number">-1</span>; i &gt;= <span class="number">0</span>; --i)</span><br><span class="line">    &#123;</span><br><span class="line">        res[i] = table[i] * product;</span><br><span class="line">        prodct *= elements[i];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="盛水"><a href="#盛水" class="headerlink" title="盛水"></a>盛水</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003092700.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">trap</span><span class="params">(<span class="keyword">int</span> A[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n &lt;= <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left_max = <span class="number">0</span>, right_max = <span class="number">0</span>, wate = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; dp(n, <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i)</span><br><span class="line">    &#123;</span><br><span class="line">        dp[i] = left_max;</span><br><span class="line">        <span class="keyword">if</span> (A[i] &gt; left_max)</span><br><span class="line">            left_max = A[i];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n<span class="number">-1</span>; i &gt;= <span class="number">0</span>; --i)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (min(right_max, dp[i]) &gt; A[i])</span><br><span class="line">        	water += min(right_max, dp[i]) - A[i];</span><br><span class="line">        <span class="keyword">if</span> (A[i] &gt; right_max)</span><br><span class="line">            right_max = A[i];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191003093259.png" alt=""> </p>
<h2 id="Tallest-stack-of-boxes"><a href="#Tallest-stack-of-boxes" class="headerlink" title="Tallest stack of boxes"></a>Tallest stack of boxes</h2><p>Given a set of boxes, each one has a square bottom and height of 1. Please write a function to return the tallest stack of these boxes. The constraint is that a box can be put on top only when its square bottom is restrictively smaller.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">vector</span>&lt;Box&gt; createStackDP( Box boxes[], <span class="keyword">const</span> <span class="keyword">int</span> num, Box bottom, <span class="built_in">unordered_map</span>&lt; Box, <span class="built_in">vector</span>&lt;Box&gt; &gt;&amp; stackCache) &#123;</span><br><span class="line">    <span class="built_in">vector</span>&lt;Box&gt; max_stack;</span><br><span class="line">    <span class="keyword">int</span> max_height = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">vector</span>&lt;Box&gt; new_stack;</span><br><span class="line">  </span><br><span class="line">    <span class="comment">// memorization</span></span><br><span class="line">    <span class="keyword">if</span>( stackCache.count( bottom ) &gt; <span class="number">0</span> )</span><br><span class="line">        <span class="keyword">return</span> stackCache[ bottom ];</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">for</span>( <span class="keyword">int</span> i = <span class="number">0</span>; i &lt; num; i++ ) &#123;</span><br><span class="line">            <span class="keyword">if</span>( Box[i].canBeAbove( bottom ) ) &#123;</span><br><span class="line">                <span class="comment">// solve subproblem</span></span><br><span class="line">                new_stack = createStackDP( boxes, num, Box[i], stackCache );</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>( new_stack.size() &gt; max_height ) &#123;</span><br><span class="line">                max_height = new_stack.size();</span><br><span class="line">                max_stack = new_stack;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  </span><br><span class="line">    max_stack.insert( max_stack.begin(), bottom );</span><br><span class="line">    stackCache[ bottom ] = max_stack;</span><br><span class="line">    <span class="keyword">return</span> max_stack;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="Word-Break-Ⅱ"><a href="#Word-Break-Ⅱ" class="headerlink" title="Word Break Ⅱ"></a>Word Break Ⅱ</h2><p>Given a string and a dictionary of words, please write a function to add space into the string, such that the string can be completely segmented into several words, where every word appears in the given dictionary.</p>
<p><strong>代码实现</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; wordBreak(<span class="built_in">string</span> s, <span class="built_in">unordered_set</span>&lt;<span class="built_in">string</span>&gt; &amp;dict, <span class="built_in">unordered_map</span>&lt;<span class="built_in">string</span>,<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; &gt;&amp; cache) &#123;</span><br><span class="line">    <span class="comment">// memorization</span></span><br><span class="line">    <span class="keyword">if</span>(cache.count(s))</span><br><span class="line">        <span class="keyword">return</span> cache[s];</span><br><span class="line">        </span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; vs;</span><br><span class="line">        </span><br><span class="line">    <span class="keyword">if</span>(s.empty()) &#123;</span><br><span class="line">        vs.push_back(<span class="built_in">string</span>());</span><br><span class="line">        <span class="keyword">return</span> vs;</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> len = <span class="number">1</span>; len &lt;= s.size(); ++len ) &#123;</span><br><span class="line">        <span class="built_in">string</span> prefix = s.substr(<span class="number">0</span>,len);</span><br><span class="line">        <span class="keyword">if</span>(dict.count(prefix) &gt; <span class="number">0</span>) &#123;          </span><br><span class="line">            <span class="built_in">string</span> suffix = s.substr(len);</span><br><span class="line"></span><br><span class="line">            <span class="comment">// solve subproblem</span></span><br><span class="line">            <span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; segments = wordBreak(suffix,dict,cache);          </span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; segments.size(); ++i) &#123;</span><br><span class="line">                <span class="keyword">if</span>(segments[i].empty()) </span><br><span class="line">                    vs.push_back(prefix);</span><br><span class="line">                <span class="keyword">else</span> </span><br><span class="line">                    vs.push_back(prefix + <span class="string">" "</span> + segments[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">    cache[s] = vs;</span><br><span class="line">    <span class="keyword">return</span> vs;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    
    
    

    
      <div>
        <div id="wechat_subscriber" style="display: block; padding: 10px 0; margin: 20px auto; width: 100%; text-align: center">
    <img id="wechat_subscriber_qcode" src="/images/wechat-qcode.jpg" alt="zxp wechat" style="width: 200px; max-width: 100%;"/>
    <div>欢迎关注微信公众号！</div>
</div>

      </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div></div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/WeChatpay.jpg" alt="zxp 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/Alipay.jpg" alt="zxp 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    zxp
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://zxpgo.github.io/2019/10/12/算法和数据结构/" title="算法和数据结构">https://zxpgo.github.io/2019/10/12/算法和数据结构/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tag/C/" rel="tag"># C++</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/10/08/索引底层原理与优化/" rel="next" title="索引底层原理与优化">
                <i class="fa fa-chevron-left"></i> 索引底层原理与优化
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/10/27/Public auditing for cloud storage/" rel="prev" title="Public auditing for cloud storage">
                Public auditing for cloud storage <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zODgxNC8xNTM0Mg=="></div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.gif"
                alt="zxp" />
            
              <p class="site-author-name" itemprop="name">zxp</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">176</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">48</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://blog.csdn.net/qq_25774883" target="_blank" title="CSDN">
                      
                        <i class="fa fa-fw fa-globe"></i>CSDN</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/zxpgo/zxpgo" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-globe"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.linkedin.com/feed/" target="_blank" title="LinkedIn">
                      
                        <i class="fa fa-fw fa-globe"></i>LinkedIn</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="1165772354@qq.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-inline">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                友情链接
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://theme-next.iissnan.com" title="Next主题" target="_blank">Next主题</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://blog.rexking6.top" title="青爷博客" target="_blank">青爷博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://me.csdn.net/download/qq_25774883" title="CSDN下载" target="_blank">CSDN下载</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.livere.com/" title="来必力" target="_blank">来必力</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://tongji.baidu.com/web/welcome/login" title="百度统计" target="_blank">百度统计</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leancloud.cn/" title="LeanCloud" target="_blank">LeanCloud</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://ibruce.info/2015/04/04/busuanzi/" title="不蒜子" target="_blank">不蒜子</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leetcode-cn.com/" title="LeetCode" target="_blank">LeetCode</a>
                  </li>
                
              </ul>
            </div>
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#实现Memmove"><span class="nav-number">1.</span> <span class="nav-text">实现Memmove</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#C语言的陷阱"><span class="nav-number">1.1.</span> <span class="nav-text">C语言的陷阱</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#内存重叠"><span class="nav-number">1.1.1.</span> <span class="nav-text">内存重叠</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#正确写法"><span class="nav-number">1.2.</span> <span class="nav-text">正确写法</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#面试考察的变成基本功"><span class="nav-number">2.</span> <span class="nav-text">面试考察的变成基本功</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#代码风格"><span class="nav-number">2.1.</span> <span class="nav-text">代码风格</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实战算法策略"><span class="nav-number">2.2.</span> <span class="nav-text">实战算法策略</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#排列组合模板"><span class="nav-number">2.3.</span> <span class="nav-text">排列组合模板</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#全排列"><span class="nav-number">2.3.1.</span> <span class="nav-text">全排列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#组合问题"><span class="nav-number">2.3.2.</span> <span class="nav-text">组合问题</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Array-amp-String"><span class="nav-number">3.</span> <span class="nav-text">Array &amp; String</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#入门题看String-match"><span class="nav-number">3.1.</span> <span class="nav-text">入门题看String match</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#暴力求解"><span class="nav-number">3.1.0.1.</span> <span class="nav-text">暴力求解</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Rabin-Karp"><span class="nav-number">3.1.0.2.</span> <span class="nav-text">Rabin-Karp</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Array"><span class="nav-number">3.2.</span> <span class="nav-text">Array</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#二维数组"><span class="nav-number">3.2.1.</span> <span class="nav-text">二维数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#vector"><span class="nav-number">3.2.2.</span> <span class="nav-text">vector</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Hash-Table"><span class="nav-number">3.2.3.</span> <span class="nav-text">Hash Table</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#碰撞"><span class="nav-number">3.2.3.1.</span> <span class="nav-text">碰撞</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#string"><span class="nav-number">3.3.</span> <span class="nav-text">string</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#字符串中字符是否唯一"><span class="nav-number">3.4.</span> <span class="nav-text">字符串中字符是否唯一</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#两个字符串的是否为排列"><span class="nav-number">3.5.</span> <span class="nav-text">两个字符串的是否为排列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#字符串包含"><span class="nav-number">3.6.</span> <span class="nav-text">字符串包含</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#anagram-字谜"><span class="nav-number">3.7.</span> <span class="nav-text">anagram(字谜)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#两数之和在数组中"><span class="nav-number">3.8.</span> <span class="nav-text">两数之和在数组中</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#数组中连续序列"><span class="nav-number">3.9.</span> <span class="nav-text">数组中连续序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Longest-Common-SubString最长相同子字符串"><span class="nav-number">3.10.</span> <span class="nav-text">Longest Common SubString最长相同子字符串</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#链表"><span class="nav-number">4.</span> <span class="nav-text">链表</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#栈和队列"><span class="nav-number">5.</span> <span class="nav-text">栈和队列</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二叉树"><span class="nav-number">6.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#分治算法"><span class="nav-number">6.1.</span> <span class="nav-text">分治算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#二分查找树"><span class="nav-number">6.2.</span> <span class="nav-text">二分查找树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#平衡二叉树"><span class="nav-number">6.3.</span> <span class="nav-text">平衡二叉树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#求二叉树中路径"><span class="nav-number">6.4.</span> <span class="nav-text">求二叉树中路径</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#二叉搜索树的中序遍历的下一个元素"><span class="nav-number">6.5.</span> <span class="nav-text">二叉搜索树的中序遍历的下一个元素</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最近的公共节点"><span class="nav-number">6.6.</span> <span class="nav-text">最近的公共节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#重构二叉树"><span class="nav-number">6.7.</span> <span class="nav-text">重构二叉树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#之字形打印二叉树"><span class="nav-number">6.8.</span> <span class="nav-text">之字形打印二叉树</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#排序"><span class="nav-number">7.</span> <span class="nav-text">排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#内排序"><span class="nav-number">7.1.</span> <span class="nav-text">内排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#归并排序"><span class="nav-number">7.1.1.</span> <span class="nav-text">归并排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序"><span class="nav-number">7.1.2.</span> <span class="nav-text">快速排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速选择排序"><span class="nav-number">7.1.3.</span> <span class="nav-text">快速选择排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#桶排序"><span class="nav-number">7.1.4.</span> <span class="nav-text">桶排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#基数排序"><span class="nav-number">7.1.5.</span> <span class="nav-text">基数排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#外排序"><span class="nav-number">7.2.</span> <span class="nav-text">外排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#堆和堆排序"><span class="nav-number">7.3.</span> <span class="nav-text">堆和堆排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#堆实现"><span class="nav-number">7.3.1.</span> <span class="nav-text">堆实现</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#堆排序"><span class="nav-number">7.3.2.</span> <span class="nav-text">堆排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#c-中堆和优先级队列"><span class="nav-number">7.3.3.</span> <span class="nav-text">c++中堆和优先级队列</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二分搜索"><span class="nav-number">8.</span> <span class="nav-text">二分搜索</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#数组中下标等于对应元素值"><span class="nav-number">8.1.</span> <span class="nav-text">数组中下标等于对应元素值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#寻找峰值"><span class="nav-number">8.2.</span> <span class="nav-text">寻找峰值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#旋转有序数组中查找"><span class="nav-number">8.3.</span> <span class="nav-text">旋转有序数组中查找</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#范围搜索"><span class="nav-number">8.4.</span> <span class="nav-text">范围搜索</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#矩阵查找"><span class="nav-number">8.5.</span> <span class="nav-text">矩阵查找</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#搜索矩阵"><span class="nav-number">8.6.</span> <span class="nav-text">搜索矩阵</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#求平方根"><span class="nav-number">8.7.</span> <span class="nav-text">求平方根</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最新的请求"><span class="nav-number">8.8.</span> <span class="nav-text">最新的请求</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#人的年龄排序"><span class="nav-number">8.9.</span> <span class="nav-text">人的年龄排序</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#大规模和内存有限的问题"><span class="nav-number">9.</span> <span class="nav-text">大规模和内存有限的问题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#社交网络"><span class="nav-number">9.1.</span> <span class="nav-text">社交网络</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#检测重复元素"><span class="nav-number">9.2.</span> <span class="nav-text">检测重复元素</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现表的合并"><span class="nav-number">9.3.</span> <span class="nav-text">实现表的合并</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#动态规划和递归"><span class="nav-number">10.</span> <span class="nav-text">动态规划和递归</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#记忆化搜索"><span class="nav-number">11.</span> <span class="nav-text">记忆化搜索</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#算法策略比较"><span class="nav-number">12.</span> <span class="nav-text">算法策略比较</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#爬楼梯"><span class="nav-number">12.1.</span> <span class="nav-text">爬楼梯</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#第n个素数"><span class="nav-number">12.2.</span> <span class="nav-text">第n个素数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#分割单词"><span class="nav-number">12.3.</span> <span class="nav-text">分割单词</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#回文切割-Palindrome-Partition"><span class="nav-number">12.4.</span> <span class="nav-text">回文切割(Palindrome Partition)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#唯一的路径"><span class="nav-number">12.5.</span> <span class="nav-text">唯一的路径</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#唯一路径Ⅱ"><span class="nav-number">12.6.</span> <span class="nav-text">唯一路径Ⅱ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最小的路径和"><span class="nav-number">12.7.</span> <span class="nav-text">最小的路径和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#跳跃游戏"><span class="nav-number">12.8.</span> <span class="nav-text">跳跃游戏</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#三角形最小值"><span class="nav-number">12.9.</span> <span class="nav-text">三角形最小值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#唯一二叉搜索树"><span class="nav-number">12.10.</span> <span class="nav-text">唯一二叉搜索树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#硬币置换"><span class="nav-number">12.11.</span> <span class="nav-text">硬币置换</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#最长子序列问题"><span class="nav-number">13.</span> <span class="nav-text">最长子序列问题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#最长子序列"><span class="nav-number">13.1.</span> <span class="nav-text">最长子序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#加油站"><span class="nav-number">13.2.</span> <span class="nav-text">加油站</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最长公共子序列"><span class="nav-number">13.3.</span> <span class="nav-text">最长公共子序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#除本身之外的乘积"><span class="nav-number">13.4.</span> <span class="nav-text">除本身之外的乘积</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#盛水"><span class="nav-number">13.5.</span> <span class="nav-text">盛水</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Tallest-stack-of-boxes"><span class="nav-number">13.6.</span> <span class="nav-text">Tallest stack of boxes</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Word-Break-Ⅱ"><span class="nav-number">13.7.</span> <span class="nav-text">Word Break Ⅱ</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div>
<script async src="https//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<i class="fa fa-user-md"></i><span id="busuanzi_container_site_pv" style='display:none'>
    本站总访问量 <span id="busuanzi_value_site_pv"></span> 
    <span class="post-meta-divider">|</span>
</span>
<span id="busuanzi_container_site_uv" style='display:none'>
    访问人数 <span id="busuanzi_value_site_uv"></span>
</span>
</div>


<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<div class="copyright">&copy; 2018-8 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-"></i> Power by 
  </span>
  <span class="author" itemprop="copyrightHolder">zxp</span>
  
  
</div>









        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  




  
  <div id="lv-container" data-uid="MTAyMC8zODgxNC8xNTM0Mg==">
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
	</div>
  











  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "default";
      
          pbOptions.boxForm = "vertical";
      
          pbOptions.position = "top";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=5.1.4"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=5.1.4"></script>


  
  <script type="text/javascript" src="/js/src/exturl.js?v=5.1.4"></script>


  
  
  	 <!-- custom analytics part create by xiamo -->
<script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
<script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
<script>
function showTime(Counter) {
	var query = new AV.Query(Counter);
	$(".leancloud_visitors").each(function() {
		var url = $(this).attr("id").trim();
		query.equalTo("url", url);
		query.find({
			success: function(results) {
				if (results.length == 0) {
					var content = $(document.getElementById(url)).text() + ' 0';
					$(document.getElementById(url)).text(content);
					return;
				}
				for (var i = 0; i < results.length; i++) {
					var object = results[i];
					var content = $(document.getElementById(url)).text() + ' ' + object.get('time');
					$(document.getElementById(url)).text(content);
				}
			}
		});

	});
}

</script>
  
</body>
</html>
